# -*- coding=utf-8 -*-
# 假设按照升序排序的数组在预先未知的某个点上进行了旋转
# ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )
# 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1
# 你可以假设数组中不存在重复的元素
# 你的算法时间复杂度必须是 O(log n) 级别

# 示例 1:
# 输入: nums = [4,5,6,7,0,1,2], target = 0
# 输出: 4

# 示例 2:
# 输入: nums = [4,5,6,7,0,1,2], target = 3
# 输出: -1

# class Solution(object):
#     def search(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: int
#         """
#         if len(nums) == 0:
#             return -1;

#         l = 0;
#         r = len(nums) - 1;
#         if nums[l] == target:
#             return l;

#         if nums[r] == target:
#             return r;

#         while (l + r) // 2 != l:
#             helf = (l + r) // 2;
#             print [l, r, helf];

#             if nums[l] == target:
#                 return l;

#             if nums[r] == target:
#                 return r;

#             if nums[helf] == target:
#                 return helf;

#             if target > nums[r] and target < nums[l]:
#                 return -1;

#             if nums[helf] > nums[l]:
#                 if target > nums[l] and target < nums[helf]:
#                     r = helf;
#                 else:
#                     l = helf;
#                 continue;

#             if nums[helf] < nums[r]:
#                 if target > nums[helf] and target < nums[r]:
#                     l = helf;
#                 else:
#                     r = helf;
#                 continue;

#         return -1;

# 学习到的内容
# 1、 A<B<C这种写法
# 2、 边界的处理，上面的算法比对l和r，通过mid向2边靠，导致出现死循环的问题([1,3], 2)
#    而下面这个算法通过比对mid，然后通过mid + 1或mid - 1向2边靠，完美解决了上面的问题
#    并且通过l<=r解决了跳出循环的条件问题
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1;

        l = 0;
        r = len(nums) - 1;
        while l <= r:
            mid = (l + r) / 2;
            print [l, r, mid];
            if nums[mid] == target:
                return mid;
            # 注意：
            # 这里使用nums[mid] >= nums[l]而不是nums[mid] > nums[l]
            # 因为当mid==l的情况发生时，上面的代码保证了l已经参加过比对
            # 而我们需要保证r也要参加入比对，所以当mid==l时，我们要让l = mid + 1得以执行
            if nums[mid] >= nums[l]:
                if nums[l] <= target <= nums[mid]:
                    r = mid - 1;
                else:
                    l = mid + 1;
            else:
                if nums[mid] <= target <= nums[r]:
                    l = mid + 1;
                else:
                    r = mid -1;
        return -1;



t = Solution();
print t.search([3,1], 1);
